//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 子数组 是数组中的一个连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：nums = [5,4,-1,7,8]
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -10⁴ <= nums[i] <= 10⁴ 
// 
//
// 
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。 
// Related Topics 数组 分治 动态规划 👍 4864 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution53 {
    /**
     * 动态规划
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        //dp[i]表示以nums[i-1]结尾的子数组的最大和
        int[] dp = new int[nums.length+1];
        dp[0] = 0;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i <= nums.length; i++){
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i-1];
            } else {
                dp[i] = nums[i-1];
            }
            if(dp[i] > result) result = dp[i];
        }
//        注意最后的结果可不是dp[nums.size()]！ ，而是dp[6]。
//
//        在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
//
//        那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
        return result;
    }

    /**
     * 贪心
     */
    public int maxSubArray1(int[] nums) {
       int sum = nums[0];//记录已经遍历的子数组的最大和
       int result = Integer.MIN_VALUE;
       for(int i = 1; i < nums.length; i++){
           if(sum >0){
               sum+=nums[i];
           } else {
               sum=nums[i];
           }
           if(sum > result) result = sum;
       }
       return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
